#include<vector>
using namespace std;
class Solution {
private:
    int action[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
    void pacificAtlanticCore(vector<vector<int>>& matrix, vector<vector<bool>>& flags,
        int row, int col, int rows, int cols) {
        for (int i = 0; i < 4; ++i) {
            int next_row = row + action[i][0];
            int next_col = col + action[i][1];
            if (next_row >= 0 && next_row < rows && next_col >= 0 && next_col < cols
                && !flags[next_row][next_col] && matrix[next_row][next_col] >= matrix[row][col]) {
                flags[next_row][next_col] = true;
                pacificAtlanticCore(matrix, flags, next_row, next_col, rows, cols);
            }
        }
    }
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<int>> res;
        if (matrix.size() < 1 || matrix[0].size() < 1)
            return res;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<bool>> pacific;
        vector<vector<bool>> atlantic;
        for (int i = 0; i < rows; ++i) {
            pacific.push_back(vector<bool>(cols, false));
            atlantic.push_back(vector<bool>(cols, false));
        }
        for (int i = 0; i < rows; ++i) {
            pacific[i][0] = true;
            pacificAtlanticCore(matrix, pacific, i, 0, rows, cols);
            atlantic[i][cols - 1] = true;
            pacificAtlanticCore(matrix, atlantic, i, cols-1, rows, cols);
        }
        for (int i = 0; i < cols; ++i) {
            pacific[0][i] = true;
            pacificAtlanticCore(matrix, pacific, 0, i, rows, cols);
            atlantic[rows-1][i] = true;
            pacificAtlanticCore(matrix, atlantic, rows - 1, i, rows, cols);
        }
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (pacific[i][j] && atlantic[i][j])
                    res.push_back(vector<int>{i, j});
            }
        }
        return res;
    }
};
/*class Solution {
private:
    int action[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
    void pacificAtlanticCore(vector<vector<int>>& matrix, vector<vector<bool>>& flags,
        int row, int col,int rows,int cols,
        vector<vector<bool>>&lt, vector<vector<bool>>&rb) {
        if (!lt[row][col]|| !rb[row][col]) {
            if (row == 0 || col == 0)
                lt[row][col] = true;
            if (row == rows - 1 || col == cols - 1)
                rb[row][col] = true;
            flags[row][col] = true;
            for (int i = 0; i < 4; ++i) {
                if (lt[row][col] && rb[row][col])
                    break;
                int next_row = row + action[i][0];
                int next_col = col + action[i][1];
                if (next_row >= 0&& next_row<rows&&next_col>=0&&next_col<cols
                    && !flags[next_row][next_col] && matrix[next_row][next_col] <= matrix[row][col]) {
                    pacificAtlanticCore(matrix, flags, next_row, next_col, rows, cols, lt, rb);
                    if (lt[next_row][next_col])
                        lt[row][col] = true;
                    if (rb[next_row][next_col])
                        rb[row][col] = true;
                }
            }
            flags[row][col] = false;
        }
    }

public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<int>> res;
        if (matrix.size() < 1 || matrix[0].size() < 1)
            return res;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<bool>> flags;
        vector<vector<bool>> lt;
        vector<vector<bool>> rb;
        for (int i = 0; i < rows; ++i) {
            flags.push_back(vector<bool>(cols, false));
            lt.push_back(vector<bool>(cols, false));
            rb.push_back(vector<bool>(cols, false));
        }

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                pacificAtlanticCore(matrix, flags, row, col, rows, cols, lt, rb);
                if (lt[row][col]&& rb[row][col])
                    res.push_back(vector<int>{row, col});
            }
        }
        return res;
    }
};*/

//int main() {
//    vector<vector<int>> matrix;
//    matrix.push_back(vector<int>{1, 2, 2, 3, 5});
//    matrix.push_back(vector<int>{3, 2, 3, 4, 4});
//    matrix.push_back(vector<int>{2, 4, 5, 3, 1});
//    matrix.push_back(vector<int>{6, 7, 1, 4, 5});
//    matrix.push_back(vector<int>{5, 1, 1, 2, 4});
//
//    Solution sol;
//    sol.pacificAtlantic(matrix);
//}